package one.three.nine;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.StdIn;

public class Parehthese {

	static class Stack<Item> implements Iterable<Item> {

		private Node<Item> first;
		private int n;

		public Stack() {
			first = null;
			n = 0;
		}

		public boolean isEmpty() {
			return first == null;
		}

		public int size() {
			return n;
		}

		public void push(Item item) {
			Node oldfirst = first;
			first = new Node();
			first.item = item;
			first.next = oldfirst;
			n++;
		}

		public Item pop() {
			if (isEmpty()) {
				throw new NoSuchElementException("Stack underflow");
			}
			Item item = (Item) first.item;
			first = first.next;
			n--;
			return item;
		}

		@Override
		public Iterator<Item> iterator() {

			return new LinkedIterator<Item>(first);
		}

		@Override
		public String toString() {
			if (first != null) {
				String s = "";
				for (Item e : this) {
					s += " " + e + " ";
				}
				return s;
			}
			return "";
		}

		private class Node<Item> {
			Item item;
			Node<Item> next;
		}

		private class LinkedIterator<Item> implements Iterator<Item> {
			private Node<Item> current;

			public LinkedIterator(Node<Item> first) {
				this.current = first;
			}

			@Override
			public boolean hasNext() {

				return current != null;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}

			@Override
			public Item next() {
				if (!hasNext()) {
					throw new NoSuchElementException();
				}
				Item item = current.item;
				current = current.next;
				return item;
			}
		}

	}

	public static void main(String[] args) {
		String s, e0, e1, e2;
		// s="-";
		// System.out.println(s.matches("[+|\\-|*|/]"));

		String[] a = StdIn.readAllStrings();
		System.out.println(Arrays.toString(a));
		Stack<String> stack = new Stack<String>();
		for (int i = 0; i < a.length; i++) {
			System.out.println("\n\n");
			s = a[i];
			System.out.println("s:" + s + ",stack:" + stack.toString());
			if (s.matches("\\d+") || s.matches("[+|\\-|*|/]")) {
				stack.push(s);
			}
			if (s.equals(")")) {
				e0 = stack.pop();
				e1 = stack.pop();
				e2 = stack.pop();
				stack.push("(" + e2 + e1 + e0 + ")");
			}
			System.out.println("\n\n");
		}
		System.out.println(stack.pop());

	}

}
